Digital halftoning is a printing technique being widely used in printing computer printer-outs, printed materials, books, newspapers, and magazines, for example. When printing the aforesaid items, original images are changed into halftone images initially. This technique which is to transform an appearance of a continuous tone image into a halftone image is called halftoning.
There are various kinds of halftoning methods, including ordered dithering, error diffusion, dot diffusion, and so on. The ordered dithering is a parallel processing method. Although the ordered dithering has an advantage of possessing a higher processing efficiency, the halftone images acquired by using the ordered dithering, however, are in poor quality. The error diffusion being used is resulting in a better halftone image quality, however, the error diffusion is lacking an advantage of parallel processing. The dot diffusion possesses a harmonious proportion in the image quality and image processing efficiency, however, a serious problem of a periodic appearance occurs with the halftone images generated by using the dot diffusion. These are reasons that the dot diffusion is unable to replace the error diffusion and has not become a mainstream in the market.
FIG. 1A is a diagram showing an original image. FIGS. 1B to 1D are diagrams showing halftone images respectively acquired by performing ordered dithering, error diffusion, and dot diffusion to the original image. As shown in FIG. 1D, the halftone image acquired by using the dot diffusion is provided with a periodic dot distribution and the texture is quite unnatural.
In the following paragraphs, a basic concept of dot diffusion will be described. Referring to FIG. 2, an original image of size P×Q is divided into a plurality of non-overlapping blocks of size M×N. Each block is processed with the dot diffusion, independently. Then, the halftone results for each block are combined according to their original positions and thereby obtaining the halftone image corresponding to the original image. Two important media called a class matrix (CM) and a diffused matrix (DM), which are respectively illustrated in FIGS. 3A and 3B as an example, are used in the dot diffusion process. The class matrix is the same size as each divided M×N block, and all the blocks use the same class matrix. As shown in FIG. 3A, the class matrix records a sequence to process each pixel in an image block. A small number means the corresponding pixel is processed in advance and a large number means the corresponding pixel is processed relatively late. As shown in FIG. 3B, the diffused matrix records diffused weightings for propagating errors to neighbor pixels. A notation x denotes a current processing pixel.
FIG. 4 is a flow chart of the dot diffusion utilized for image processing. Here, a white pixel is defined as 255 and a black pixel as 0. The variable xi,j denotes a grayscale value of a pixel as an input and x′i,j is the diffused error accumulated from the neighbor processed pixels. The variable vi,j is the modified gray output and yi,j represents a binary output, i.e. a pixel value of the halftone image, at the position (i, j). In addition, the variable ei,j denotes the difference between the modified gray output vi,j and the binary output yi,j, and the relationships of vi,j, yi,j and ei,j are represented as below:
                                          v                          i              ,              j                                =                                    x                              i                ,                j                                      +                          x                              i                ,                j                            ′                                      ,                              where            ⁢                                                  ⁢                          x                              i                ,                j                            ′                                =                                    ∑                              m                ,                                  n                  ∈                  R                                                      ⁢                          ∑                                                                    e                                                                  i                        +                        m                                            ,                                              j                        +                        n                                                                              ×                                      dw                                          m                      ,                      n                                                                      sum                                                                        (        1        )                                                      e                          i              ,              j                                =                                    v                              i                ,                j                                      -                          y                              i                ,                j                                                    ,                              where            ⁢                                                  ⁢                          y                              i                ,                j                                              =                      {                                                                                0                    ,                                                                                                              v                                              i                        ,                        j                                                              <                    128                                                                                                                    255                    ,                                                                                                              v                                              i                        ,                        j                                                              ≥                    128                                                                                                          (        2        )            where the variable dwm,n is a diffused weighting in the diffused matrix, and the corresponding position of the diffused weighting is defined as below:
                    [                                                            dw                                                      -                    1                                    ,                                      -                    1                                                                                                      dw                                                      -                    1                                    ,                  0                                                                                    dw                                                      -                    1                                    ,                  1                                                                                                        dw                                  0                  ,                                      -                    1                                                                                      x                                                      dw                                  0                  ,                  1                                                                                                        dw                                  1                  ,                                      -                    1                                                                                                      dw                                  1                  ,                  0                                                                                    dw                                  1                  ,                  1                                                                    ]                            (        3        )            where the symbol x denotes the current processing pixel, and the values in the eight-neighbor connections are diffused proportions, i.e. the diffused weightings.
Note that, the error can only diffuse or propagate to neighbor pixels that have not yet been binarized, i.e. those unprocessed pixels. The key to determine whether the neighbor pixels are processed is to determine whether the member in the class matrix possesses a smaller value than the member corresponding to the current processing pixel. In the equation (1), the variable sum=Σm=−11Σn=−11dwm,n is the summation of the diffused weightings corresponding to those unprocessed pixels. As shown in FIGS. 3A and 3B, the error corresponding to the member value 7 of the class matrix can be propagated to the pixels corresponding to the member values 10, 15, 18, 23, and 31. The value of sum which is associated with the member value 7 in the class matrix is 7.
As mentioned above, a serious problem of a periodic appearance occurs with the halftone images generated by the dot diffusion. The periodic pattern is mainly caused by the tiling manner. FIG. 5 is a diagram showing a class tiling map used in a traditional dot diffusion. The whole sheet of original image is processed in parallel wherein each divided image block is processed according to the processing order recorded in each class matrix of the class tiling map. As shown in FIG. 5, the traditional class tiling map is constructed by arranging a plurality of class matrixes in a non-overlapping and orthogonal manner, and arranging one by one until it coincides with the size of the original image. Here, the four corners in one class matrix are labeled as top left (TL), bottom left (BL), top right (TL), and bottom right (BL), respectively. The corresponding positions in each class matrix are placed with members of the same processing order. For example, the members located at column 5 row 7 of each class matrix are all 39.
For the class tiling map constructed by 3×3 class matrixes in the aforesaid arrangement, as shown in FIG. 6, the distances between the members of the same processing order in a subject class matrix and neighboring class matrixes are equal to each other. This class matrix arrangement results in a high similarity of halftone for each image block and therefore brings about the periodic dot distribution formed on the whole sheet of halftone image.
To solve the aforesaid periodic problem, a conventional method is provided to select class matrixes in a limited manner and to arrange the selected class matrixes. This conventional method can ensure that the halftone images acquired by dot diffusion possess an excellent blue noise property. In this conventional method, a first step is to generate a set of class matrixes by rotating or transposing a class matrix, for example, eight class matrixes as shown in FIG. 7. Then, the class matrix arrangement is proceeded by selecting from the eight class matrixes. An example to illustrate the conventional method is as follows. Referring to FIG. 8A, solid lines indicate that those class matrixes have been arranged and dash lines indicate that the class matrix is currently proceeding to be arranged. The class matrixes are arranged in a non-overlapping and orthogonal manner. The class matrixes which are constructing the class tiling map are selected from the eight class matrixes shown in FIG. 7. When proceeding to select one class matrix, the selection of class matrix is limited, and particularly, to the types or contents of arranged neighboring class matrixes. Referring to FIGS. 7 and 8A, the limitations to the selection of current class matrix are listed below:
(1) The limitation from the class matrix CM I: the current class matrix should not be a class matrix of which the top-left corner is filled by TR, the bottom-left corner is filled by BR, or the left border is filled by TR BR or BR TR.
(2) The limitation from the class matrix CM III: the current class matrix should not be a class matrix of which the bottom-left corner is filled by TR, the bottom-right corner is filled by BR, or the bottom border is filled by TR BR or BR TR.
(3) The limitation from the class matrixes CM II and CM IV: the current class matrix should not be a class matrix of which the bottom-left corner is filled by TL, or the bottom-right corner is filled by TR.
(4) The limitation from the class matrixes CM I to CM III: the current class matrix should not be identical to any one of the class matrixes CMI to CM III.
The above limitations (1) to (3) exclude six possible choices and the class matrixes located at the positions (1, 1) and (2, 3) in FIG. 7 are remnants to be selected. Also, the class matrix located at the position (1, 1) is excluded by the above limitation (4).
As described above, in the conventional arrangement, the selection of current class matrix is extremely limited by surrounded neighboring class matrixes. The possible choices of class matrixes are mostly filtered out and therefore there are not many choices for the current class matrix. These limitations result in retrieving a periodic class tiling map. Referring to examples illustrated in FIGS. 8B to 8D, those class matrixes indicated by the same symbol with the same form or shape are identical to each other. The heavy lines indicate the border of periodic class matrixes. Apparently, this conventional method merely increases the period of class matrix arrangement, for example, increasing the period by two to four times. As can be seen, in order to reduce the periodic pattern, this method utilizes rotated or transposed class matrixes to participate the arrangement but it finally turns out just increasing the period of class matrix arrangement. The conventional arrangement has the same effect as another arrangement adopting the class matrix of a bigger size. These methods can not completely solve the periodic problem of halftone images.
Above all, the conventional arrangement utilizing the limited selection of class matrixes from rotated or transposed class matrixes merely increases the period of class matrix arrangement. The above-mentioned conventional skills are unable to solve the periodic problem of halftone images efficiently and thereby the dot diffusion is not widely used. Therefore, it is necessary to provide a technical scheme to overcome the disadvantages of the above conventional skills.